package com.company.ljh.easy;
//给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
//
// 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
//
//
//
// 示例 1：
//
// 输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
//
//
// 示例 2：
//
// 输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
//
//
// 示例 3：
//
// 输入：nums1 = [0,0], nums2 = [0,0]
//输出：0.00000
//
//
// 示例 4：
//
// 输入：nums1 = [], nums2 = [1]
//输出：1.00000
//
//
// 示例 5：
//
// 输入：nums1 = [2], nums2 = []
//输出：2.00000
// 示例 5：
//
// 输入：nums1 = [1,2,4], nums2 = [3,5]
//输出：2.00000
//
//4
//
//
// 提示：
//
//
// nums1.length == m
// nums2.length == n
// 0 <= m <= 1000
// 0 <= n <= 1000
// 1 <= m + n <= 2000
// -106 <= nums1[i], nums2[i] <= 106
//
// Related Topics 数组 二分查找 分治算法
// 👍 3363 👎 0


public class 两个正序数组中位数简单算法 {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int totalNums[] = new int[nums1.length+nums2.length/2+1];
        int m = 0;
        int n = 0;
        int index = 0;
        double mindleNumber = 0;
        while(m < nums1.length && n < nums2.length){
            totalNums[index] = nums1[m] < nums2[n]?nums1[m++]:nums2[n++];
            if (index == (nums1.length+nums2.length)/2){
                if ((nums1.length+nums2.length) % 2 == 0)
                    mindleNumber = (totalNums[index]+totalNums[index-1])/2.0;
                else
                    mindleNumber = totalNums[index];
                return mindleNumber;
            }
            index++;
        }
        while (m < nums1.length){

            totalNums[index] = nums1[m++];
            if (index == (nums1.length+nums2.length)/2){
                if ((nums1.length+nums2.length) % 2 == 0)
                    mindleNumber = (totalNums[index]+totalNums[index-1])/2.0;
                else
                    mindleNumber = totalNums[index];
                return mindleNumber;

            }
            index++;
        }
        while (n < nums2.length){
            totalNums[index] = nums2[n++];
            if (index == (nums1.length+nums2.length)/2){
                if ((nums1.length+nums2.length) % 2 == 0)
                    mindleNumber = (totalNums[index]+totalNums[index-1])/2.0;
                else
                    mindleNumber = totalNums[index];
                return mindleNumber;

            }
            index++;
        }
        return mindleNumber;
    }

    public static void main(String[] args) {
        int num1 []= new int[]{};
        int num2 []= new int[]{3,4,5};
        double medianSortedArrays = findMedianSortedArrays(num1, num2);
        System.out.println(medianSortedArrays);

    }
}
